
/*
回溯
连接：https://leetcode.cn/problems/letter-combinations-of-a-phone-number/
题目：17. 电话号码的字母组合


3. 解法：
算法思路：
每个位置可选择的字符与其他位置并不冲突，因此不需要标记已经出现的字符，只需要将每个数字对
应的字符依次填⼊字符串中进⾏递归，在回溯是撤销填⼊操作即可。
• 在递归之前我们需要定义⼀个字典 phoneMap，记录 2~9 各⾃对应的字符。
递归函数设计：void backtrack(unordered_map<char, string>& phoneMap, string& digits, int
index)
参数：index （已经处理的元素个数），ans （字符串当前状态），res （所有成⽴的字符串）；
返回值：⽆
函数作⽤：查找所有合理的字⺟组合并存储在答案列表中。
递归函数流程如下：
1. 递归结束条件：当 index 等于 digits 的⻓度时，将 ans 加⼊到 res 中并返回；
2. 取出当前处理的数字 digit，根据 phoneMap 取出对应的字⺟列表 letters；
3. 遍历字⺟列表 letters，将当前字⺟加⼊到组合字符串 ans 的末尾，然后递归处理下⼀个数字（传
⼊ index + 1，表⽰处理下⼀个数字）；
4. 递归处理结束后，将加⼊的字⺟从 ans 的末尾删除，表⽰回溯。
5. 最终返回 res 即可

画出决策树：
设计代码：
    全局变量：
        vector<string> ret;保存结果
        
        vector<string> hash;记录数字与字符串的映射
    dfs函数：
       仅需关心每一层选哪个字符串的每一个字符
    细节问题
        回溯：path为参数，每一层都是自己的，不用担心需不需要复原
        减枝:
        递归出口：pos==digit.size();


*/
class Solution {
public:
    vector<string> hash={"","","abc","def","ghi","jkl","mon","pqrs","tuv","wxyz"};
    vector<string> ret;
    vector<string> letterCombinations(string digits) {
        if(digits.empty())  
            return vector<string>();
        dfs(digits,0,"");
        return ret;
    }
    void dfs(string digits,int pos,string path)
    {
        if(pos == digits.size())
        {
            ret.push_back(path);
            return ;
        }
        int idx = digits[pos]-'0';
        string str = hash[idx];
        for(int i =0;i<str.size();i++)
        {
            dfs(digits,pos+1,path+str[i]);
        }
    }
};
